Tham khảo Cây bao trùm nhỏ nhất

  1. ↑ Fredman, M. L.; Willard, D. E. (1994), “Trans-dichotomous algorithms for minimum spanning trees and shortest paths”, Journal of Computer and System Sciences 48 (3): 533–551, MR 1279413, doi:10.1016/S0022-0000(05)80064-9 .
  2. ↑ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), “A randomized linear-time algorithm to find minimum spanning trees”, Journal of the Association for Computing Machinery 42 (2): 321–328, MR 1409738, doi:10.1145/201019.201022 
  3. ↑ Pettie, Seth; Ramachandran, Vijaya (2002), “Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms”, Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco, California, tr. 713–722 .
  4. ↑ Chazelle, Bernard (2000), “A minimum spanning tree algorithm with inverse-Ackermann type complexity”, Journal of the Association for Computing Machinery 47 (6): 1028–1047, MR 1866456, doi:10.1145/355541.355562 .
  5. ↑ Chazelle, Bernard (2000), “The soft heap: an approximate priority queue with optimal error rate”, Journal of the Association for Computing Machinery 47 (6): 1012–1027, MR 1866455, doi:10.1145/355541.355554 .
  6. ↑ Pettie, Seth; Ramachandran, Vijaya (2002), “An optimal minimum spanning tree algorithm”, Journal of the Association for Computing Machinery 49 (1): 16–34, MR 2148431, doi:10.1145/505241.505243 .
  7. ↑ Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), “Concurrent threads and optimal parallel minimum spanning trees algorithm”, Journal of the Association for Computing Machinery 48 (2): 297–323, MR 1868718, doi:10.1145/375827.375847 .
  8. ↑ Pettie, Seth; Ramachandran, Vijaya (2002), “A randomized time-work optimal parallel algorithm for finding a minimum spanning forest”, SIAM Journal on Computing 31 (6): 1879–1895, MR 1954882, doi:10.1137/S0097539700371065 .
  9. ↑ Bader, David A.; Cong, Guojing (2006), “Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs”, Journal of Parallel and Distributed Computing 66 (11): 1366–1378, doi:10.1016/j.jpdc.2006.06.001 .
  10. ↑ Dementiev, Roman; Sanders, Peter; Schultes, Dominik; Sibeyn, Jop F. (2004), “Engineering an external memory minimum spanning tree algorithm”, Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) (PDF), tr. 195–208 .
  11. ↑ Steele, J. Michael (2002), “Minimal spanning trees for graphs with random edge lengths”, Mathematics and computer science, II (Versailles, 2002), Trends Math., Basel: Birkhäuser, tr. 223–245, MR 1940139 
  12. ↑ Gabow, Harold N. (1977), “Two algorithms for generating weighted spanning trees in order”, SIAM Journal on Computing 6 (1): 139–150, MR0441784 .
  13. ↑ Eppstein, David (1992), “Finding the k smallest spanning trees”, BIT 32 (2): 237–248, MR 1172188, doi:10.1007/BF01994879 .
  14. ↑ Frederickson, Greg N. (1997), “Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees”, SIAM Journal on Computing 26 (2): 484–538, doi:10.1137/S0097539792226825, MR1438526 .
  15. ↑ Hu, T. C. (1961), “The maximum capacity route problem”, Operations Research 9 (6): 898–900, JSTOR 167055 .
  16. ↑ Spira, P. M.; Pan, A. (1975), “On finding and updating spanning trees and shortest paths”, SIAM Journal on Computing 4 (3): 375–380, MR 0378466 .
  17. ↑ Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (2001), “Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity”, Journal of the Association for Computing Machinery 48 (4): 723–760, MR 2144928, doi:10.1145/502090.502095 .

Tài liệu tham khảo

WikiPedia: Cây bao trùm nhỏ nhất http://algo2.iti.kit.edu/dementiev/files/emst.pdf http://portal.acm.org/citation.cfm?id=545477 //www.ams.org/mathscinet-getitem?mr=0378466 http://www.ams.org/mathscinet-getitem?mr=0441784 //www.ams.org/mathscinet-getitem?mr=1172188 //www.ams.org/mathscinet-getitem?mr=1279413 //www.ams.org/mathscinet-getitem?mr=1409738 http://www.ams.org/mathscinet-getitem?mr=1438526 //www.ams.org/mathscinet-getitem?mr=1866455 //www.ams.org/mathscinet-getitem?mr=1866456